package solution.pointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : wenchao.long
 * @date : Created in 2024-07-07 下午 1:59 周日
 * @description : 三数之和
 * 		<a href="https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked">三数之和</a>
 * 		1. 给数组排序 这样可以保证 循环a、b、c 可以得到一个累加的结果
 */
public class No15 {

	public static List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> res = new ArrayList<>();
		int length = nums.length;
		// 给数组排序
		Arrays.sort(nums);
		// 求三个数 a+b+c = 0
		for (int left = 0; left < length; ++left) {
			if (nums[left] > 0) {
				break;
			}
			// 重复的数据不计算
			if (left > 0 && nums[left] == nums[left - 1]) {
				continue;
			}
			int right = length - 1;
			// 计算target的值
			int target = -nums[left];
			for (int second = left + 1; second < length; ++second) {
				if (second > left + 1 && nums[second] == nums[second - 1]) {
					continue;
				}
				while (second < right && nums[second] + nums[right] > target) {
					right--;
				}
				if (second == right) {
					break;
				}
				if (nums[second] + nums[right] == target) {
					List<Integer> list = new ArrayList<>();
					list.add(nums[left]);
					list.add(nums[second]);
					list.add(nums[right]);
					res.add(list);
				}
			}
		}
		return res;
	}

	public static void main(String[] args) {
		List<List<Integer>> lists = threeSum(new int[]{-1, 0, 1, 2, -1, -4});
		System.out.println(lists);
	}
}
